package main

// 131. 分割回文串
func main() {
	b := partition("xxcc")
	for _, sb := range b {
		for _, ssb := range sb {
			print(ssb + ",")
		}
		println()
	}
}

func partition(s string) [][]string {
	var res [][]string
	n := len(s)
	f := make([][]bool, n) // 回文串字典

	for i := range f {
		f[i] = make([]bool, n)
		for j := range f[i] {
			f[i][j] = true
		}
	}

	// 根据动态规划算法 获取回纹子串
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = s[i] == s[j] && f[i+1][j-1]
		}
	}

	var split []string
	var dfs func(idx int)
	dfs = func(idx int) {
		if idx == n {
			res = append(res, append([]string{}, split...))
			return
		}
		for i := idx; i < n; i++ {
			if f[idx][i] {
				split = append(split, s[idx:i+1])
				dfs(i + 1)
				split = split[0 : len(split)-1]
			}
		}
	}

	dfs(0)

	return res
}

func partition2(s string) (ans [][]string) {
	n := len(s)
	f := make([][]bool, n)
	for i := range f {
		f[i] = make([]bool, n)
		for j := range f[i] {
			f[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = s[i] == s[j] && f[i+1][j-1]
		}
	}

	splits := []string{}
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			ans = append(ans, append([]string(nil), splits...))
			return
		}
		for j := i; j < n; j++ {
			if f[i][j] {
				splits = append(splits, s[i:j+1])
				dfs(j + 1)
				splits = splits[:len(splits)-1]
			}
		}
	}
	dfs(0)
	return
}

// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
//回文串
// 。返回 s 所有可能的分割方案。
//
//
//
//示例 1：
//
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
//示例 2：
//
//输入：s = "a"
//输出：[["a"]]
//
//
//提示：
//
//1 <= s.length <= 16
//s 仅由小写英文字母组成
